package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:给定一个候选人编号的集合candidates和一个目标数target，找出candidates
 * 中所有可以使数字和为target的组合。
 *
 * candidates中的每个数字在每个组合中只能使用一次。
 *
 * 示例1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 *
 * 提示:
 *
 * 1 <= candidates.length <= 100
 * 1 <= candidates[i] <= 50
 * 1 <= target <= 30
 *
 * author: Mr.Du
 * Date: 2022/11/7
 * Time: 21:21
 */
public class CombinationSumII {
    
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 有重复的数字，先进行排序
        Arrays.sort(candidates);
        dd(candidates,0,0,target);
        return res;
    
    }
    
    /**
     * 思路：
     *      第一步：退出条件是：sum > target(也是一种节约时间的做法，没有此判出条件也行)或者
     *      sum == target(相等时就将一个结果加入集合中),
     *      第二步：循环
     *              选择操作：
     *                  由于存在重复数字，要去重，所以每次先判断当前位置是否和它前面数字是否相等，
     *                  相等就continue，不相等就进行选择操作(加入集合中，并且进行sum+操作)，
     *              进入回溯
     *              回退操作：
     *                  就是将上面的操作选择操作进行反操作(上面加入集合，那么就取出，上面sum+，下
     *                  面就是sum-)
     * @param candidates
     * @param start     起始位置
     * @param sum       用来记录每一趟的总和
     * @param target    目标总和
     */
    public void dd(int[] candidates, int start, int sum, int target){
        if(sum > target) return;
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i < candidates.length;i++){
            if(i > start && candidates[i-1] == candidates[i]) continue;
            sum += candidates[i];
            list.add(candidates[i]);
            dd(candidates,i + 1, sum, target);
            list.removeLast();
            sum -= candidates[i];
        }
    }
}
